1
2
3 from enum import Enum
4 import datetime
5 import random
6
7 """Constants"""
8 PLAYER = 'X'
9 COMPUTER = 'O'
10 EMPTY = '_'
11 BOARD_SIZE = 5
12 NUMBER_OF_PLAYERS = 1
13 SEARCH_TIME = 5
14
15 """exception class, in case the user entered a none empty position"""
16
17 class NoneEmptyPosition(Exception):
18 pass
19
20
21 """exception class, in case the user entered number higher the board positions"""
22
23
24 class OutOfRange(Exception):
25 pass
26
27 """ enum for game state"""
28
29 class GameState(Enum):
30 tie = 'Tie'
31 notEnd = 'notEnd'
32 o = 'O' # computer won
33 x = 'X' # player won
34
35
36 """
37 this class managing the board game activities
38 """
39
40
41 class Board:
42
43 """
44 the constructor gets 1 argumnet size - the size of the board
45 it initialized the game board to be empty board (size x size)
46 and store the last move which been made in order to decide who won
47 """
48 def __init__(self, size):
49 self.mSize = size
50 self.mBoard = [[EMPTY for x in range(size)] for y in range(size)]
51 self.lastMove = None
52
53 """this function prints the game board"""
54 def print(self):
55 for i in range(self.mSize):
56 for j in range(self.mSize):
57 if j < self.mSize-1:
58 print(self.mBoard[i][j], end='|')
59 else:
60 print(self.mBoard[i][j], end='')
61 print()
62
63 """this function gets position 0 - size x size
64 and convert it to a board position
65 and return the match row and column"""
66 def getBoardPosition(self,position):
67 column = position%self.mSize
68 row = position//self.mSize
69 return row, column
70
71 """this function return the last move on the board"""
72 def getLastMove(self):
73 return self.lastMove
74
75 """this function gets number of row in the board and return the match row"""
76 def getRow(self, numberOfRow):
77 return self.mBoard[numberOfRow]
78
79 """this function gets number of column in the board and return the match column"""
80 def getColumn(self, numberOFColumn):
81 return [row[numberOFColumn] for row in self.mBoard]
82
83 """this function return the diagonals of the board"""
84 def getDiagonal(self):
85 diagonal1 = [self.mBoard[i][i] for i in range(self.mSize)]
86 diagonal2 = []
87 j = 0
88 for i in reversed(range(self.mSize)):
89 diagonal2.append(self.mBoard[i][j])
90 j += 1
91 return diagonal1, diagonal2
92
93 """this function return the main diagonal of the board, left to right"""
94 def getMainDiagonal(self):
95 return [self.mBoard[i][i] for i in range(self.mSize)]
96
97 """this function return the secondary diagonal of the board, right to left"""
98 def getSecondaryDiagonal(self):
99 diagonal = []
100 j = 0;
101 for i in reversed(range(self.mSize)):
102 diagonal.append(self.mBoard[i][j])
103 j += 1
104 return diagonal
105
106 """this function gets position and checking if the position is on the main diagonal"""
107 def checkIfOnMainDiagonal(self, position):
108 return position % (self.mSize + 1) == 0
109
110 """this function gets position and checking if the position is on the secondary diagonal"""
111 def checkIfOnSecondaryDiagonal(self, position):
112 return position % (self.mSize - 1) == 0
113
114 """this function gets position and draw 'X' on the match place on the board"""
115 def drawX(self, position):
116 self.lastMove = position
117 (row, column) = self.getBoardPosition(position)
118 self.mBoard[row][column] = PLAYER
119
120 """this function gets position and draw '_' on the match place on the board"""
121 def drawEmpty(self, position):
122 (row, column) = self.getBoardPosition(position)
123 self.mBoard[row][column] = EMPTY
124
125 """this function gets position and draw 'O' on the match place on the board"""
126 def drawO(self, position):
127 self.lastMove = position
128 (row, column) = self.getBoardPosition(position)
129 self.mBoard[row][column] = COMPUTER
130
131 """this function gets position and checking if it empty"""
132 def checkIfRubricEmpty(self, position):
133 (row, column) = self.getBoardPosition(position)
134 return self.mBoard[row][column] == EMPTY
135
136 """this function gets 2 arguments: listToBeChecked - line in the board
137 char - 'X' or 'Y' and checking if all the line filled with it"""
138 def all_same(self, listToBeChecked, char):
139 return all(x == char for x in listToBeChecked)
140
141
142 """this class handling all the game Activities"""
143
144
145 class Game:
146 """the constructor gets 2 arguments: numberOfPlayers, board size
147 also, mNamesList - store the names of the players
148 mTurn - says who have the turn to play, even -player1, odd - player2
149 mComputerFirstPosition - store the random position of the computer"""
150
151 def __init__(self, numberOfPlayers, boardSize):
152 self.mBoard = Board(boardSize)
153 self.mBoardSize = boardSize
154 self.mNumberOfPlayers = numberOfPlayers
155 self.mNamesList = [' ']*numberOfPlayers
156 self.mTurn = None
157 self.mComputerFirstPosition = None
158 self.coinFlip()
159 self.mBestMove = 0
160
161
162 """this function decide who is starting the game by coin flip,
163 if the computer won it choose random Move for the first move"""
164 def coinFlip(self):
165 turn = random.choice(['computer', 'player'])
166 if turn == 'computer':
167 self.mComputerFirstPosition = random.randrange(self.mBoard.mSize ** 2)
168 self.mTurn = 1
169 else:
170 self.mTurn = 0
171
172 """this function gets the players names and stored them"""
173 def getPlayersNames(self):
174 counter = 1
175 while counter <= self.mNumberOfPlayers:
176 try:
177 playerName = input('please enter the name of player' + str(counter))
178 if not playerName:
179 raise ValueError("field cannot be empty, please enter name")
180 if not playerName.isalpha():
181 raise ValueError("only letters are allowed")
182 if playerName in self.mNamesList:
183 raise ValueError("name already chosen please choose different name")
184
185 self.mNamesList[counter - 1] = playerName
186 counter += 1
187 except ValueError as e:
188 print(e)
189 except Exception:
190 print("unknown error")
191
192
193 """this function gets the player move from the user"""
194 def getPlayerMove(self):
195 while True:
196 try:
197 playerMove = int(input(self.mNamesList[self.mTurn] + ' please select rubric'))
198 if not (0 <= playerMove <= (self.mBoardSize ** 2 - 1)):
199 raise OutOfRange("Wrong position, please choose position 0 - " + str(self.mBoardSize ** 2 - 1))
200
201 if not self.mBoard.checkIfRubricEmpty(playerMove):
202 raise NoneEmptyPosition("this rubric taken please choose other rubric")
203
204 return playerMove
205
206 except (OutOfRange, NoneEmptyPosition) as e:
207 print(e)
208 except ValueError as e:
209 print("only numbers are allowed")
210 except Exception:
211 print("unknown error")
212
213 """ this function gets a player turn and check if the player won
214 based on his last move, it checking every line which including the last move"""
215 def checkForWin(self, turn):
216 char = ''
217 if turn % 2 == 0:
218 char = 'X'
219 else:
220 char = 'O'
221 lastMove = self.mBoard.getLastMove()
222 row, col = self.mBoard.getBoardPosition(lastMove)
223
224 if self.mBoard.all_same(self.mBoard.getRow(row), char) or \
225 self.mBoard.all_same(self.mBoard.getColumn(col), char):
226 return True
227
228 if self.mBoard.checkIfOnMainDiagonal(lastMove):
229 if self.mBoard.all_same(self.mBoard.getMainDiagonal(), char):
230 return True
231
232 if self.mBoard.checkIfOnSecondaryDiagonal(lastMove):
233 if self.mBoard.all_same(self.mBoard.getSecondaryDiagonal(), char):
234 return True
235
236 return False
237
238 """this function check if the game is tie, which means the board is filled and there is no winner"""
239 def checkForTie(self):
240 for i in range(self.mBoard.mSize ** 2):
241 if self.mBoard.checkIfRubricEmpty(i):
242 return False
243 return True
244
245 """this function compute all the valid moves on the game board and return them"""
246 def genrate(self):
247 possibleMoves = []
248 for i in range(self.mBoard.mSize ** 2):
249 if self.mBoard.checkIfRubricEmpty(i):
250 possibleMoves.append(i)
251 return possibleMoves
252
253 """this function check the game state and return it"""
254 def checkGameState(self):
255 if self.checkForWin(0):
256 return GameState.x
257
258 if self.checkForWin(1):
259 return GameState.o
260
261 if self.checkForTie():
262 return GameState.tie
263
264 return GameState.notEnd
265
266 """ this function is starting the game and managing it until it over"""
267 def start(self):
268 self.getPlayersNames()
269 while True:
270 self.mBoard.print()
271 self.mTurn %= 2
272 if self.mTurn % 2 == 0:
273 playerMove = self.getPlayerMove()
274 self.mBoard.drawX(playerMove)
275 else:
276 print('computer please select rubric')
277 if self.mComputerFirstPosition is not None:
278 computerMove = self.mComputerFirstPosition
279 self.mComputerFirstPosition = None
280 else:
281 computerMove = self.iterativeDeepSearch()
282
283 self.mBoard.drawO(computerMove)
284
285 gameResult = self.checkGameState()
286 if gameResult.value != 'notEnd':
287 self.mBoard.print()
288 if gameResult.value == 'Tie':
289 print('The game is tie')
290 else:
291 if self.mTurn % 2 == 0:
292 print(self.mNamesList[self.mTurn] + 'is the winner!')
293 else:
294 print('computer is the winner!')
295 break
296
297 self.mTurn += 1
298
299 """ this function gets 6 arguments: depth - the depth of the game tree
300 isMax - tell which side are we, the maximizer or the minimizer
301 alpha - store the best value for the maximizer
302 beta - store the best value for the minimizer
303 startTime - the time we started the search
304 timeLimit - the time we will search for the best move
305 the function tells if the moves I take is better or worse by compute the best score
306 and position in the given depth, than it return them
307 I used minmax algorithm with alpha beta pruning"""
308 def minmax2(self, depth, isMax, alpha, beta, startTime, timeLimit):
309
310 moves = self.genrate()
311 score = self.evaluate()
312 position = None
313
314 if datetime.datetime.now() - startTime >= timeLimit:
315 self.mTimePassed = True
316
317 if not moves or depth == 0 or self.mTimePassed:
318 gameResult = self.checkGameState()
319 if gameResult.value == 'X':
320 return -10**(self.mBoard.mSize+1), position
321 elif gameResult.value == 'O':
322 return 10**(self.mBoard.mSize+1), position
323 elif gameResult.value == 'Tie':
324 return 0, position
325
326 return score, position
327
328 if isMax:
329 for i in moves:
330 self.mBoard.drawO(i)
331 score, dummy = self.minmax2(depth-1, not isMax, alpha, beta, startTime, timeLimit)
332 if score > alpha:
333 alpha = score
334 position = i
335 self.mBestMove = i
336
337 self.mBoard.drawEmpty(i)
338 if beta <= alpha:
339 break
340
341 return alpha, position
342 else:
343 for i in moves:
344 self.mBoard.drawX(i)
345 score, dummy = self.minmax2(depth-1, not isMax, alpha, beta, startTime, timeLimit)
346 if score < beta:
347 beta = score
348 position = i
349 self.mBestMove = i
350 self.mBoard.drawEmpty(i)
351 if alpha >= beta:
352 break
353
354 return beta, position
355
356 """this function search the best move it find in 5 seconds.
357 The function goes as deep as possible in 5 second in the game tree
358 and return the best move"""
359 def iterativeDeepSearch(self):
360 startTime = datetime.datetime.now()
361 endTime = startTime + datetime.timedelta(0, SEARCH_TIME)
362 depth = 1
363 position = None
364 self.mTimePassed = False
365 while True:
366 currentTime = datetime.datetime.now()
367 if currentTime >= endTime:
368 break
369 best, position = self.minmax2(depth, True, -10000000, 10000000, currentTime, endTime-currentTime)
370 depth += 1
371
372 if position is None:
373 position = self.mBestMove
374
375 return position
376
377 """this function gets a board line and calculate how many
378 'X', 'O' and empty rubrics"""
379 def calculateLine(self, line):
380 oSum = line.count(COMPUTER)
381 xSum = line.count(PLAYER)
382 EmptySum = line.count(EMPTY)
383 return oSum, xSum, EmptySum
384
385 """this function gets a board line and calculate it score"""
386 def getScoreLine(self, line):
387 score = 0
388 oSum, xSum, EmptySum = self.calculateLine(line)
389 if xSum == 0 and oSum != 0:
390 if oSum == self.mBoard.mSize:
391 score += 11 ** (oSum - 1)
392 score += 10 ** (oSum - 1)
393 if oSum == 0 and xSum != 0:
394 score += -(10 ** (xSum - 1))
395 return score
396
397 """this function evaluate the game board and return the score"""
398 def evaluate(self):
399 score = 0
400 for i in range(self.mBoard.mSize):
401 score += self.getScoreLine(self.mBoard.getRow(i))
402 score += self.getScoreLine(self.mBoard.getColumn(i))
403
404 diagonals = self.mBoard.getDiagonal()
405 for i in range(2):
406 score += self.getScoreLine(diagonals[i])
407 return score
408
409
410 game = Game(NUMBER_OF_PLAYERS, BOARD_SIZE)
411 game.start()
